One of the major trends of the last decade in computer science has been the increasing popularity of the "object-oriented" paradigm. While there is little consensus regarding the meaning of this term, any object-oriented system must be concerned with the allocation and maintenance of storage for "objects" where an "object" is data that share a particular attribute and occupy a contiguous region of memory. Objects are not permitted to overlap. "Live" objects are those needed in the computational process currently being performed by a computer system.
If all objects in a system are permanent, then there is no concern about memory management. The space assigned to each object at system start-up need never be reclaimed. In most real systems, however, live objects have varying lifetimes that cannot be predicted in advance. In such systems, some method of recognizing expired ("dead") objects and evicting them from memory is necessary if memory resources are to be conserved.
"Garbage" is a term of art in computer technology which refers to data stored in computer system memory that is no longer being used in the performance of an application program. "Garbage collection" is the process of locating data in dynamically-allocated memory that is no longer being used and reclaiming the memory to satisfy future allocation requests.
Since garbage collection greatly reduces low-level programming detail, it offers the potential of significant programmer productivity gains. By freeing programmers from this low-level detail, garbage collection encourages programmers and system designers to dedicate their intellectual efforts to higher-level pursuits, such as the design of fundamental algorithms, user interfaces, and general program functionality. Also, by eliminating many low-level programming concerns, garbage collection reduces the likelihood of programming errors. And finally, dynamic memory management based on copying-types of garbage-collection algorithms are capable of delivering much higher storage throughput than explicit allocation and allocation revocation, reference-count storage reclamation, and even stack allocation. Together these benefits of garbage collection combine to offer improved software functionality and reliability for lower development costs.
Garbage collection is accomplished by copying live objects that are stored in one region of memory to a second region, thereby leaving dead objects behind in the first region. When the copying process has been completed, the dead objects are disposed of, and the garbage-collecting process continues with the copying of live objects in the second region back to the first. An up-to-date list of live objects is maintained by the central processing unit and forwarded to the garbage-collecting facility at the start of each garbage-collection cycle.
The copying process requires that memory space be allocated to the objects being copied in the region of memory to which the objects are being transferred. The information needed for allocating memory space to objects is contained in the header (i.e. the first word) of each object. Thus, the garbage-collecting control unit must be able to access the header of each live object being transferred to another region of memory. This requirement poses a problem in the case of live objects that are discovered as a result of examining the objects on the CPU's list in that the object headers are not readily available.
The list of objects supplied by the CPU is essentially a list of pointers to addresses contained within live objects. Objects on the CPU's list may contain pointers to data within other objects and these "referenced" objects are also live and must also be copied even though they do not appear on the CPU's list of live objects. In order that garbage collecting may proceed expeditiously, it is necessary that pointers to data within objects be translatable into pointers to object headers.